The present disclosure relates to the field of software processing. In particular, the present disclosure relates to dynamic instruction sequence selection performed during compiling of program code.
In typical software applications, an application is developed in what is referred to as a high level language that can be relatively independent of the type of hardware used to execute the application. The high level language can be compiled or otherwise translated into a hardware specific low level language instructions. The low level instructions can be loaded into a storage device, such as memory, and hardware can execute the instructions.
The development of increasingly complex hardware and processors enable the development of complex instructions sets that facilitate execution of particular types of applications. For example, a low level language associated with a processor that is configured to facilitate digital signal processing can implement complex instructions directed towards common digital signal processing operations. In digital signal processing, a typical operation requires a multiplication immediately followed by an accumulation that can be executed as an addition step. The multiply and accumulate may need to be performed hundreds or thousands of times within a particular application. A low level language may allow the multiplication and accumulation to be implemented in a single instruction, such as a MADD instruction, thereby reducing the total number of instructions needed in the application. Of course, the low level language can also include separate multiply and add instructions that can be used in instances where a distinct multiplication or addition is needed.
Because a low level language may include complex instructions that perform a combination of functions, there is the possibility of performing an identical operation using two or more equivalent instruction sequences. In the example provided above, a multiply and accumulate operation can be scheduled as a single MADD instruction or alternatively as separate multiply and add instructions.
Thus, many times a particular computation in an application can be compiled in multiple ways, using different instructions or sequence of instructions. Traditionally, the selection of instruction sequences corresponding to the computation is performed prior to the scheduling of instructions. However, in many cases, it is not possible to determine a priori which instruction sequence results in an optimal schedule for a given program.
The alternative instruction sequences that correspond to the same computation may utilize different hardware resources. A particular processor configuration can have multiple execution units and the execution of particular instructions may or may not be constrained to particular execution units. For example, some instructions may be limited to execute on specific execution units within a processor, while other instructions may be executed by any of a number of execution units.
The hardware constraints associated with particular instruction sequences further complicates instruction selection and scheduling. In some cases, it may be beneficial to use an instruction sequence that uses specific resources. In other cases, it may be beneficial to use an alternative instruction sequence that utilizes other machine resources. For example, in one case, it may be beneficial to select and schedule an instruction sequence that reduces dependency depth. In another case, it may be preferable to schedule an alternative instruction sequence for the similar computation because the alternative instruction sequence reduces the register pressure.
Thus, the problem of selecting an instruction sequence for a particular computation for which alternatives exist is complicated by the potential for different hardware utilization. The changes in allocation and consumption of machine resources makes it difficult to select a particular instruction sequence that would result in an optimal instruction sequence for the changing conditions occurring within the application.